#include <vector>

using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int a)
    :val(a), left(nullptr), right(nullptr)
    {}
};
class Solution
{
public:
    TreeNode *Create(vector<int> &preorder, vector<int> &inorder, int &root, int start, int end)
    {
        if (start > end)
        {
            return nullptr;
        }

        TreeNode *_root = new TreeNode(preorder[root]);
        root++;

        int inPos = start;
        while(inPos < end)
        {
            if (inorder[inPos] == _root->val)
            {
                break;
            }
            ++inPos;
        }

        _root->left = Create(preorder, inorder, root, start, inPos - 1);
        _root->right = Create(preorder, inorder, root, inPos + 1, end);

        return _root;
    }

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {
        int root = 0;
        return Create(preorder, inorder, root, 0, preorder.size() - 1);
    }
};